#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Software: PyCharm
# @Version : Python-
# @Author  : Shengji He
# @Email   : hsjbit@163.com
# @File    : PartitionLabels.py
# @Time    : 2020/10/22 10:23
# @Description:
from typing import List


class Solution:
    def partitionLabels(self, S: str) -> List[int]:
        """
        A string S of lowercase English letters is given. We want to partition this string into as many parts as
        possible so that each letter appears in at most one part, and return a list of integers representing the
        size of these parts.

        Example 1:
            Input: S = "ababcbacadefegdehijhklij"
            Output: [9,7,8]
            Explanation:
                The partition is "ababcbaca", "defegde", "hijhklij".
                This is a partition so that each letter appears in at most one part.
                A partition like "ababcbacadefegde", "hijhklij" is incorrect, because it splits S into less parts.

        Note:
            - S will have length in range [1, 500].
            - S will consist of lowercase English letters ('a' to 'z') only.

        :param S:
        :return:
        """
        last = [0] * 26
        for i, ch in enumerate(S):
            last[ord(ch) - ord('a')] = i
        ans = []

        start = end = 0
        for i, ch in enumerate(S):
            end = max(end, last[ord(ch) - ord('a')])
            if i == end:
                ans.append(end - start + 1)
                start = end + 1
        return ans


if __name__ == '__main__':
    solution = Solution()
    S = 'ababcbacadefegdehijhklij'
    print(solution.partitionLabels(S))
    print('done')
